/*
 * @lc app=leetcode.cn id=153 lang=cpp
 *
 * [153] 寻找旋转排序数组中的最小值
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int findMin(vector<int> &nums)
    {
        int l = 0, r = nums.size() - 1;
        int ret = nums[0];
        while (l <= r)
        {
            int mid = l + (r - l) / 2;
            if(mid == l)
            {
                ret = min(min(ret, nums[l]), nums[r]);
            }
            if(nums[mid] > nums[l])
            {//l至mid是升序的
                ret = min(nums[l], ret);
                l = mid + 1;
            }
            else
            {
                //mid至r是升序的
                ret = min(nums[mid], ret);
                r = mid - 1;
            }
        }

        return ret;
    }
};
// @lc code=end
